{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Operations to Make Network Connected"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: makeConnected"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #连通网络的操作次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>用以太网线缆将&nbsp;<code>n</code>&nbsp;台计算机连接成一个网络，计算机的编号从&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n-1</code>。线缆用&nbsp;<code>connections</code>&nbsp;表示，其中&nbsp;<code>connections[i] = [a, b]</code>&nbsp;连接了计算机&nbsp;<code>a</code>&nbsp;和&nbsp;<code>b</code>。</p>\n",
    "\n",
    "<p>网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。</p>\n",
    "\n",
    "<p>给你这个计算机网络的初始布线&nbsp;<code>connections</code>，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回&nbsp;-1 。&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/11/sample_1_1677.png\" style=\"height: 167px; width: 570px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 4, connections = [[0,1],[0,2],[1,2]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/11/sample_2_1677.png\" style=\"height: 175px; width: 660px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>线缆数量不足。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= connections.length &lt;= min(n*(n-1)/2, 10^5)</code></li>\n",
    "\t<li><code>connections[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= connections[i][0], connections[i][1]&nbsp;&lt; n</code></li>\n",
    "\t<li><code>connections[i][0] != connections[i][1]</code></li>\n",
    "\t<li>没有重复的连接。</li>\n",
    "\t<li>两台计算机不会通过多条线缆连接。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-operations-to-make-network-connected](https://leetcode.cn/problems/number-of-operations-to-make-network-connected/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-operations-to-make-network-connected](https://leetcode.cn/problems/number-of-operations-to-make-network-connected/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[0,1],[0,2],[1,2]]', '6\\n[[0,1],[0,2],[0,3],[1,2],[1,3]]', '6\\n[[0,1],[0,2],[0,3],[1,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "        def get_root(num, relations) -> int:\n",
    "            while relations[num] != -1:\n",
    "                num = relations[num]\n",
    "            return num\n",
    "        relations = [-1] * n\n",
    "        for connection in connections:\n",
    "            flag_1, flag_2 = get_root(connection[0], relations), get_root(connection[1], relations)\n",
    "            if flag_1 != flag_2:\n",
    "                relations[flag_1] = flag_2\n",
    "        count = 0\n",
    "        for i in range(len(relations)):\n",
    "            if relations[i] == -1:\n",
    "                count += 1\n",
    "        return count - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind(object):\n",
    "    def __init__(self, n: int):\n",
    "        self.parent_seq = [i for i in range(n)]\n",
    "        self.count = n\n",
    "    \n",
    "    def find(self, x: int):\n",
    "        elem, parent = x, self.parent_seq[x]\n",
    "        while elem != parent:\n",
    "            self.parent_seq[elem] = self.parent_seq[parent]\n",
    "            elem = self.parent_seq[elem]\n",
    "            parent = self.parent_seq[elem]\n",
    "        return parent\n",
    "    \n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return \n",
    "        \n",
    "        self.parent_seq[root_x] = root_y\n",
    "        self.count -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        dup_connects = 0\n",
    "        for x, y in connections:\n",
    "            if uf.is_connected(x, y):\n",
    "                dup_connects += 1\n",
    "            else:\n",
    "                uf.union(x, y)\n",
    "\n",
    "        single_parts = uf.count - 1\n",
    "        if dup_connects >= single_parts:\n",
    "            return single_parts\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "\n",
    "        parent = [-1] * n\n",
    "        height = [0] * n \n",
    "\n",
    "        def find(x):\n",
    "            while parent[x] != -1:\n",
    "                x = parent[x]\n",
    "            return x\n",
    "        def union(x, y):\n",
    "            x = find(x)\n",
    "            y = find(y)\n",
    "            if x == y: return \n",
    "            # parent[x] = y\n",
    "            if height[x] < height[y]:\n",
    "                parent[x] = y\n",
    "            elif height[x] > height[y]:\n",
    "                parent[y] = x\n",
    "            else:\n",
    "                parent[x] = y\n",
    "                height[y] += 1\n",
    "            \n",
    "        m = len(connections)\n",
    "        if m < n - 1:\n",
    "            return -1\n",
    "        for x, y in connections:\n",
    "            union(x,y)\n",
    "        res = -1\n",
    "        for i in range(n):\n",
    "            if parent[i] == -1:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        将联通的电脑并入同一集合, 同时记录多余的连接线数量\n",
    "        \"\"\"\n",
    "        def find(x: int):\n",
    "            if x != f[x]:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        def union(x: int, y: int):\n",
    "            nonlocal lines\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx == ry:  # 如果两台计算机同属一个集合, 则表明它们之间连接线是多余的\n",
    "                lines += 1\n",
    "            else:\n",
    "                f[rx] = ry  # 否则将它们合并如集合\n",
    "\n",
    "        f = [i for i in range(n)]\n",
    "        lines = 0\n",
    "        for x, y in connections:\n",
    "            union(x, y)\n",
    "\n",
    "        sets = 0  # 统计互不连通的集合数量\n",
    "        for i, x in enumerate(f):\n",
    "            if x == i:\n",
    "                sets += 1\n",
    "        # print(lines, sets)\n",
    "\n",
    "        if lines < sets - 1:\n",
    "            return -1\n",
    "        return sets - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        m = len(connections)\n",
    "\n",
    "        if m < n-1:\n",
    "            return -1\n",
    "        f = [i for i in range(n)]\n",
    "        def find(x):\n",
    "            if f[x] != x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        \n",
    "        tmp = 0\n",
    "\n",
    "        for a, b in connections:\n",
    "            fa = find(a)\n",
    "            fb = find(b)\n",
    "            if fa != fb:\n",
    "                # tmp -= 1\n",
    "                f[fa] = fb\n",
    "            else:\n",
    "                tmp += 1\n",
    "        ls = 0\n",
    "        for i in range(n):\n",
    "            if f[i] == i:\n",
    "                ls += 1\n",
    "        print(f)\n",
    "        print(ls, tmp)\n",
    "        if ls -1 > tmp:\n",
    "            return -1\n",
    "        else:\n",
    "            return ls-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dsuFind(self, pa, x):\n",
    "        i = pa[x]\n",
    "        while pa[i] != i:\n",
    "            i = pa[i]\n",
    "        return i\n",
    "    def dsuUnion(self, pa, x, y):\n",
    "        xi = self.dsuFind(pa, x)\n",
    "        yi = self.dsuFind(pa, y)\n",
    "        pa[xi] = yi\n",
    "\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        # 拔出所有可拔线缆后变成并查集问题\n",
    "        dsu_pa = list(range(n))\n",
    "        area_count = n\n",
    "        area_line_count = [0] * n\n",
    "        area_node_count = [0] * n\n",
    "        area_free_line_count = [0] * n\n",
    "        for i in connections:\n",
    "            xi = self.dsuFind(dsu_pa, i[0])\n",
    "            yi = self.dsuFind(dsu_pa, i[1])\n",
    "            dsu_pa[xi] = yi\n",
    "            if xi != yi:\n",
    "                area_count -= 1\n",
    "            self.dsuUnion(dsu_pa, i[0], i[1])\n",
    "        for i in connections:\n",
    "            area = self.dsuFind(dsu_pa, i[0])\n",
    "            area_line_count[area] += 1\n",
    "        for i in dsu_pa:\n",
    "            area = self.dsuFind(dsu_pa, i)\n",
    "            area_node_count[area] += 1\n",
    "        print(area_line_count)\n",
    "        print(area_node_count)\n",
    "\n",
    "        free_line_count = 0\n",
    "        for i in range(n):\n",
    "            if area_node_count[i] == 0:\n",
    "                continue\n",
    "            free_line_count += area_line_count[i] - (area_node_count[i] - 1)\n",
    "        print(free_line_count)\n",
    "        print(area_count)\n",
    "\n",
    "        if (area_count - 1) <= free_line_count:\n",
    "            return area_count - 1\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n-1:\n",
    "            return -1 \n",
    "        UF = UnionFind(n)\n",
    "        for a, b in connections:\n",
    "            UF.unionSet(a, b)\n",
    "        \n",
    "        return UF.numSets-1\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int, m: int=None) -> None:\n",
    "        \"\"\"\n",
    "        build m disjoint sets from n nodes\n",
    "        T: O(N)\n",
    "        \"\"\"\n",
    "        self.parents = list(range(n))  \n",
    "        self.ranks = [0] * n            \n",
    "        self.sizeSets = [1] * n         # sizeSets[i]: size of disjoint set rooted at vertex i\n",
    "        self.numSets = n                # number of disjoint sets\n",
    "        self.edgeCount = [0] * n        # edgeCount[i]: number of edges in disjoint set rooted at vertex i\n",
    "\n",
    "    \n",
    "    def findSet(self, i: int) -> int:\n",
    "        \"\"\"return root of node i's set\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "           path-compression  \n",
    "           Recursion\n",
    "        \"\"\"\n",
    "        if self.parents[i] == i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parents[i] = self.findSet(self.parents[i])\n",
    "            return self.parents[i]\n",
    "        \n",
    "\n",
    "    def findSet(self, i: int) -> int:\n",
    "        \"\"\"return root of node i's set\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "           path-compression: keep the trees very flat\n",
    "           Iteration\n",
    "        \"\"\"\n",
    "        children = []   # 记录从当前节点到根节点路径上的所有节点\n",
    "\n",
    "        # 从当前节点开始，向上查找父节点\n",
    "        while i != self.parents[i]:\n",
    "            children.append(i)\n",
    "            i = self.parents[i]\n",
    "\n",
    "        # 路径压缩：一条路径上的所有节点都变成叶节点，直接连接根节点\n",
    "        # 路径压缩后，树会变矮，但不更新这些节点的rank值，继续用于union()\n",
    "        for child in children:\n",
    "            self.parents[child] = i \n",
    "        \n",
    "        # 返回根节点\n",
    "        return i\n",
    "    \n",
    "    def unionSet(self, i: int, j: int) -> None:\n",
    "        \"\"\"若节点i和节点j来自2个不同的互斥集合，将两个集合合并 \n",
    "           union by rank   矮树作为高树的子树\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        ip, jp = self.findSet(i), self.findSet(j)\n",
    "\n",
    "        # 若两个节点来自同一互斥集合，返回\n",
    "        if ip == jp:\n",
    "            self.edgeCount[ip] += 1\n",
    "            return \n",
    "\n",
    "        # 若A树矮，B树高，A树连到B树的根节点上，新树rank不变\n",
    "        if self.ranks[ip] < self.ranks[jp]:\n",
    "            self.parents[ip] = jp\n",
    "            self.sizeSets[jp] += self.sizeSets[ip]\n",
    "            self.edgeCount[jp] += self.edgeCount[ip] + 1\n",
    "\n",
    "        # 若B树矮，A树高，B树连到A树的根节点上，新树rank不变\n",
    "        elif self.ranks[jp] < self.ranks[ip]:\n",
    "            self.parents[jp] = ip\n",
    "            self.sizeSets[ip] += self.sizeSets[jp]\n",
    "            self.edgeCount[ip] += self.edgeCount[jp] + 1\n",
    "\n",
    "        # 若两树等高，任选一种方案，新树 rank +1\n",
    "        else:\n",
    "            self.parents[jp] = ip\n",
    "            self.sizeSets[ip] += self.sizeSets[jp]\n",
    "            self.edgeCount[ip] += self.edgeCount[jp] + 1\n",
    "            self.ranks[ip] += 1\n",
    "\n",
    "        # 互斥集总数-1\n",
    "        self.numSets -= 1\n",
    "    \n",
    "    def isSameSet(self, i: int, j: int) -> bool:\n",
    "        \"\"\"判断节点i和节点j是否属于同一集合\n",
    "           T: O(α(N) first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        # path compression twice\n",
    "        return self.findSet(i) == self.findSet(j)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "\n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "\n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        a = set()\n",
    "        for i in connections:\n",
    "            a.add(i[0])\n",
    "            a.add(i[1])\n",
    "        b = set()\n",
    "        for i in range(n):\n",
    "            if i not in a:\n",
    "                b.add(i)\n",
    "        a = list(b)\n",
    "        ans = 0\n",
    "        margin = 0\n",
    "        line_sys = UnionFind(n)\n",
    "        for i in connections:\n",
    "            if not line_sys.unite(i[0], i[1]):\n",
    "                margin += 1\n",
    "        for i in range(n-1):\n",
    "            if line_sys.unite(i, i + 1):\n",
    "                if margin:\n",
    "                    margin -= 1\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        UF = UnionFind(n)\n",
    "        for a, b in connections:\n",
    "            UF.unionSet(a, b)\n",
    "        \n",
    "        need = UF.numSets-1\n",
    "\n",
    "        redundant = 0\n",
    "        roots = set([UF.findSet(i) for i in range(n)])\n",
    "        for root in roots:\n",
    "            redundant += UF.edgeCount[root] - (UF.sizeSets[root] - 1)\n",
    "\n",
    "        return need if redundant >= need else -1\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int, m: int=None) -> None:\n",
    "        \"\"\"\n",
    "        build m disjoint sets from n nodes\n",
    "        T: O(N)\n",
    "        \"\"\"\n",
    "        self.parents = list(range(n))  \n",
    "        self.ranks = [0] * n            \n",
    "        self.sizeSets = [1] * n         # sizeSets[i]: size of disjoint set rooted at vertex i\n",
    "        self.numSets = n                # number of disjoint sets\n",
    "        self.edgeCount = [0] * n        # edgeCount[i]: number of edges in disjoint set rooted at vertex i\n",
    "\n",
    "    \n",
    "    def findSet(self, i: int) -> int:\n",
    "        \"\"\"return root of node i's set\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "           path-compression  \n",
    "           Recursion\n",
    "        \"\"\"\n",
    "        if self.parents[i] == i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parents[i] = self.findSet(self.parents[i])\n",
    "            return self.parents[i]\n",
    "        \n",
    "\n",
    "    def findSet(self, i: int) -> int:\n",
    "        \"\"\"return root of node i's set\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "           path-compression: keep the trees very flat\n",
    "           Iteration\n",
    "        \"\"\"\n",
    "        children = []   # 记录从当前节点到根节点路径上的所有节点\n",
    "\n",
    "        # 从当前节点开始，向上查找父节点\n",
    "        while i != self.parents[i]:\n",
    "            children.append(i)\n",
    "            i = self.parents[i]\n",
    "\n",
    "        # 路径压缩：一条路径上的所有节点都变成叶节点，直接连接根节点\n",
    "        # 路径压缩后，树会变矮，但不更新这些节点的rank值，继续用于union()\n",
    "        for child in children:\n",
    "            self.parents[child] = i \n",
    "        \n",
    "        # 返回根节点\n",
    "        return i\n",
    "    \n",
    "    def unionSet(self, i: int, j: int) -> None:\n",
    "        \"\"\"若节点i和节点j来自2个不同的互斥集合，将两个集合合并 \n",
    "           union by rank   矮树作为高树的子树\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        ip, jp = self.findSet(i), self.findSet(j)\n",
    "\n",
    "        # 若两个节点来自同一互斥集合，返回\n",
    "        if ip == jp:\n",
    "            self.edgeCount[ip] += 1\n",
    "            return \n",
    "\n",
    "        # 若A树矮，B树高，A树连到B树的根节点上，新树rank不变\n",
    "        if self.ranks[ip] < self.ranks[jp]:\n",
    "            self.parents[ip] = jp\n",
    "            self.sizeSets[jp] += self.sizeSets[ip]\n",
    "            self.edgeCount[jp] += self.edgeCount[ip] + 1\n",
    "\n",
    "        # 若B树矮，A树高，B树连到A树的根节点上，新树rank不变\n",
    "        elif self.ranks[jp] < self.ranks[ip]:\n",
    "            self.parents[jp] = ip\n",
    "            self.sizeSets[ip] += self.sizeSets[jp]\n",
    "            self.edgeCount[ip] += self.edgeCount[jp] + 1\n",
    "\n",
    "        # 若两树等高，任选一种方案，新树 rank +1\n",
    "        else:\n",
    "            self.parents[jp] = ip\n",
    "            self.sizeSets[ip] += self.sizeSets[jp]\n",
    "            self.edgeCount[ip] += self.edgeCount[jp] + 1\n",
    "            self.ranks[ip] += 1\n",
    "\n",
    "        # 互斥集总数-1\n",
    "        self.numSets -= 1\n",
    "    \n",
    "    def isSameSet(self, i: int, j: int) -> bool:\n",
    "        \"\"\"判断节点i和节点j是否属于同一集合\n",
    "           T: O(α(N) first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        # path compression twice\n",
    "        return self.findSet(i) == self.findSet(j)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections)<n-1: return -1 \n",
    "        edges, cnt, visited = [[] for _ in range(n)], 0, [0 for _ in range(n)]\n",
    "        for x,y in connections:\n",
    "            edges[x].append(y)\n",
    "            edges[y].append(x)\n",
    "        for i in range(n):\n",
    "            if visited[i]==0:\n",
    "                cnt, visited[i] = cnt+1, 1\n",
    "                queue = deque([i])\n",
    "                while queue:\n",
    "                    tmp = queue.popleft()\n",
    "                    for j in edges[tmp]:\n",
    "                        if visited[j]==0:\n",
    "                            visited[j]=1\n",
    "                            queue.append(j)\n",
    "        return cnt-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        fa = [i for i in range(n)]\n",
    "        cnt = 0\n",
    "        unconnected = []\n",
    "        for i in range(n-len(connections),n):\n",
    "            unconnected.append(i)\n",
    "        for edge in connections:\n",
    "            a = edge[0]\n",
    "            b = edge[1]\n",
    "            if self.find(a-1, fa)==self.find(b-1, fa):\n",
    "                cnt += 1\n",
    "            else:\n",
    "                self.union(a-1, b-1, fa)\n",
    "        nums = 0\n",
    "        for i in range(n):\n",
    "            if fa[i]==i:\n",
    "                nums+=1\n",
    "        if cnt >= nums-1:\n",
    "            return nums-1\n",
    "        return -1\n",
    "\n",
    "    def find(self,x,fa):\n",
    "        if x== fa[x]:\n",
    "            return x\n",
    "        return self.find(fa[x], fa)\n",
    "    \n",
    "    def union(self,x,y,fa):\n",
    "        fa[self.find(x, fa)] = self.find(y, fa)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < (n - 1):\n",
    "            return -1\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        def union(x, y):\n",
    "            rootX = find(x)\n",
    "            rootY = find(y)\n",
    "            parent[rootX] = rootY\n",
    "\n",
    "        def find(x):\n",
    "            origin = parent[x]\n",
    "            if origin != parent[origin]:\n",
    "                parent[x] = find(origin)\n",
    "            return parent[x]\n",
    "        \n",
    "        operations = 0\n",
    "        roots = set()\n",
    "        visited = set()\n",
    "        for x, y in connections:\n",
    "            union(x, y)\n",
    "            if find(x) == find(y):\n",
    "                operations += 1\n",
    "\n",
    "        for x, y in connections:\n",
    "            visited.add(x)\n",
    "            visited.add(y)\n",
    "            roots.add(find(x))\n",
    "            roots.add(find(y))\n",
    "\n",
    "        components = n - len(visited) + len(roots)\n",
    "        print(components)\n",
    "        return components - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        removed = 0\n",
    "        edges = [[] for _ in range(n)]\n",
    "        visited = [0] * n\n",
    "        for c in connections:\n",
    "            edges[c[0]].append(c[1])\n",
    "            edges[c[1]].append(c[0])\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                subcount = 0\n",
    "                subremoved = 0\n",
    "                q = collections.deque([i])\n",
    "                visited[i] = 1\n",
    "                while q:\n",
    "                    front = q.popleft()\n",
    "                    subcount += 1\n",
    "                    for v in edges[front]:\n",
    "                        subremoved += 1\n",
    "                        if not visited[v]:\n",
    "                            visited[v] = 1\n",
    "                            q.append(v)\n",
    "                removed += (subremoved // 2 - subcount + 1)\n",
    "                count += 1\n",
    "        if count - 1 <= removed:\n",
    "            return count - 1\n",
    "        else:\n",
    "            return -1\n",
    "                \n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if (len(connections) < n-1):\n",
    "            return -1\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for start, end in connections:\n",
    "            graph[start].append(end)\n",
    "            graph[end].append(start)\n",
    "        \n",
    "        isVisited = [False] * n\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if isVisited[i]:\n",
    "                continue\n",
    "            cnt += 1\n",
    "            BFS = [i]\n",
    "            isVisited[i] = True\n",
    "            while BFS:\n",
    "                node = BFS.pop(0)\n",
    "                for child in graph[node]:\n",
    "                    if not isVisited[child]:\n",
    "                        isVisited[child] = True\n",
    "                        BFS.append(child)\n",
    "        return cnt - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "    \n",
    "    def find(self,x):\n",
    "        root = x\n",
    "        while self.father[root] != None:\n",
    "            root = self.father[root]\n",
    "        #路径压缩\n",
    "        while x != root:\n",
    "            original_root = self.father[x]\n",
    "            self.father[x] = root\n",
    "            x = original_root\n",
    "        return root\n",
    "        \n",
    "    def merge(self,a,b):\n",
    "        root_a = self.find(a)\n",
    "        root_b = self.find(b)\n",
    "        if root_a != root_b:\n",
    "            self.father[root_a] = root_b\n",
    "\n",
    "    def add(self,x):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "    \n",
    "    def isconnected(self,a,b):\n",
    "        return self.find(a) == self.find(b) and a in self.father and b in self.father\n",
    "\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        count0,count = 0,0\n",
    "        for c in connections:\n",
    "            self.add(c[0])\n",
    "            self.add(c[1])\n",
    "            if not self.isconnected(c[0],c[1]):\n",
    "                self.merge(c[0],c[1])\n",
    "                count0 += 1\n",
    "            else:\n",
    "                count += 1\n",
    "        return n-1-count0 if count0 + count >= n-1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "        self.size = 0\n",
    "\n",
    "    def find(self,x):\n",
    "        root = x\n",
    "\n",
    "        while self.father[root] != None:\n",
    "            root = self.father[root]\n",
    "\n",
    "        # 路径压缩\n",
    "        while x != root:\n",
    "            original_father = self.father[x]\n",
    "            self.father[x] = root\n",
    "            x = original_father\n",
    "         \n",
    "        return root\n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        root_x,root_y = self.find(x),self.find(y)\n",
    "        \n",
    "        if root_x != root_y:\n",
    "            self.father[root_x] = root_y\n",
    "            self.size -= 1\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def add(self, x):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "        self.size += 1\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections)  < n - 1:\n",
    "            return -1\n",
    "\n",
    "        uf = UnionFind()\n",
    "\n",
    "        for j in range(n):\n",
    "            uf.add(j)\n",
    "\n",
    "        for i in connections:           \n",
    "            if uf.is_connected(i[0], i[1]) is False:\n",
    "                uf.merge(i[0], i[1])\n",
    "\n",
    "        if uf.size == 1:\n",
    "            return 0\n",
    "        else:\n",
    "            return uf.size - 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class UnionFind:\n",
    "        def __init__(self,data):\n",
    "            self.father = {}\n",
    "            for node in data:\n",
    "                self.father[node] = node\n",
    "\n",
    "        def find(self,node):\n",
    "            if node != self.father[node]:\n",
    "                self.father[node] = self.find(self.father[node])\n",
    "            return self.father[node]\n",
    "\n",
    "        def union(self,node1,node2):\n",
    "            self.father[self.find(node2)] = self.find(node1)\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        e = len(connections)\n",
    "        if e < n-1:\n",
    "            return -1\n",
    "        uf  = Solution.UnionFind(range(n))\n",
    "        for x,y in connections:\n",
    "            print(x,y)\n",
    "            uf.union(x,y)\n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            s.add(uf.find(i))\n",
    "        #print(uf.father)\n",
    "        return len(s) - 1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        par = [_ for _ in range(n)]\n",
    "        def find_root(i):\n",
    "            if par[i]!=i:\n",
    "                par[i] = find_root(par[i])\n",
    "            return par[i]\n",
    "\n",
    "        edge_cnt = {}\n",
    "        for i, j in connections:\n",
    "            par[find_root(i)] = find_root(j)\n",
    "            # print(i, par[i])\n",
    "            edge_cnt[i] = edge_cnt.get(i, 0)+1\n",
    "            edge_cnt[j] = edge_cnt.get(j, 0)+1\n",
    "\n",
    "        cluster_size = {}\n",
    "        cluster_edge_cnt = {}\n",
    "        for i in range(n):\n",
    "            par[i] = find_root(i)\n",
    "            cluster_size[par[i]] = cluster_size.get(par[i], 0)+1\n",
    "            cluster_edge_cnt[par[i]] = cluster_edge_cnt.get(par[i], 0)+edge_cnt.get(i, 0)\n",
    "\n",
    "        cluster_cnt = len(set(par))\n",
    "        extra_edge = 0\n",
    "        for i in set(par):\n",
    "            extra_edge += cluster_edge_cnt.get(i, 0)//2-(cluster_size[i]-1)\n",
    "\n",
    "        # print(par)\n",
    "        if extra_edge >= cluster_cnt-1:\n",
    "            return cluster_cnt-1\n",
    "        else:\n",
    "            return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}       \n",
    "        self.cnt = 0\n",
    "        self.line = {} \n",
    "        self.size = {}\n",
    "    \n",
    "    def find(self, x):        \n",
    "        self.add(x)\n",
    "        # 一次性平铺          \n",
    "        if self.father[x] != x:\n",
    "            self.father[x] = self.find(self.father[x])\n",
    "        \n",
    "        return self.father[x]               \n",
    "\n",
    "    def merge(self, x, y):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if self.line[root_x] > self.line[root_y]:\n",
    "            root_x, root_y = root_y, root_x    \n",
    "    \n",
    "        if root_x!=root_y:\n",
    "            self.father[root_x] = root_y   \n",
    "            self.cnt -= 1  \n",
    "            self.line[root_y] += self.line[root_x] + 1\n",
    "            self.size[root_y] += self.size[root_x]\n",
    "            \n",
    "        else:\n",
    "            self.line[root_y] += 1      \n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x)==self.find(y)\n",
    "\n",
    "    def add(self, x):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = x     \n",
    "            self.cnt += 1\n",
    "            self.line[x] = 0\n",
    "            self.size[x] = 1\n",
    "            \n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        uf = UnionFind()\n",
    "        \n",
    "        for x,y in connections:\n",
    "            uf.merge(x,y)\n",
    "        \n",
    "        rest_line = 0\n",
    "        visited = set()\n",
    "        for i in range(n):\n",
    "            root = uf.find(i)\n",
    "            if root in visited:\n",
    "                continue\n",
    "                \n",
    "            rest_line += uf.line[root] - uf.size[root] + 1\n",
    "            visited.add(root)\n",
    "            # print(i,root,uf.line[root],uf.size[root])\n",
    "            # print(rest_line)\n",
    "        \n",
    "        # print(uf.cnt)\n",
    "        if rest_line >= uf.cnt - 1:\n",
    "            return uf.cnt - 1\n",
    "        \n",
    "        return -1\n",
    "        \n",
    "            \n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        # build graph\n",
    "        graph=[[]for _ in range(n)]\n",
    "        for node1,node2 in connections:\n",
    "            graph[node1].append(node2)\n",
    "            graph[node2].append(node1)\n",
    "        # search how many islands\n",
    "        visited=[False for _ in range(n)]\n",
    "        islands=[]#record all islands, format [{island1},{island2},...]\n",
    "        for node in range(n):\n",
    "            if visited[node]:continue\n",
    "            island=set()\n",
    "            frontier={node}\n",
    "            while frontier:#keep finding neighbor\n",
    "                island|=frontier\n",
    "                new_frontier=set()\n",
    "                for node1 in frontier:\n",
    "                    for node2 in graph[node1]:\n",
    "                        if visited[node2]:continue\n",
    "                        new_frontier.add(node2)\n",
    "                        visited[node2]=True\n",
    "                frontier=new_frontier\n",
    "            else:#if no more neighbor, record this island\n",
    "                islands.append(island)\n",
    "        # how many cables to spare\n",
    "        cable_spare_total=0#global count of spare cable\n",
    "        for island in islands:      \n",
    "            # cable count is graph count/2, because -> <- count twice\n",
    "            cable_count=0\n",
    "            for node in island:\n",
    "                cable_count+=len(graph[node])\n",
    "            cable_count//=2\n",
    "            cable_require=len(island)-1\n",
    "            cable_spare_total+=cable_count-cable_require\n",
    "        # if enough, then answer==count_island-1, else answer==-1\n",
    "        if cable_spare_total>=len(islands)-1:\n",
    "            answer=len(islands)-1\n",
    "        else:answer=-1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "        edges = [[] for _ in range(n)]\n",
    "        for a, b in connections:\n",
    "            edges[a].append(b)\n",
    "            edges[b].append(a)\n",
    "        visited = set()\n",
    "\n",
    "        def bfs(i):\n",
    "            deq = collections.deque([i])\n",
    "            visited.add(i)\n",
    "            while deq:\n",
    "                i = deq.popleft()\n",
    "                for j in edges[i]:\n",
    "                    if j not in visited:\n",
    "                        deq.append(j)\n",
    "                        visited.add(j)\n",
    "            return\n",
    "        \n",
    "        group = 0\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                bfs(i)\n",
    "                group += 1\n",
    "        return group - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        cnt = set()\n",
    "        for x, y in connections:\n",
    "            cnt.add(x)\n",
    "            cnt.add(y)\n",
    "        return n - len(cnt) if len(connections) >= n - 1 else -1\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1: return -1\n",
    "        visited = [0] * n\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in connections:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if visited[i]:\n",
    "                return \n",
    "            for j in g[i]:\n",
    "                visited[i] = 1\n",
    "                dfs(j)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if visited[i] == 0:\n",
    "                dfs(i)\n",
    "                ret += 1\n",
    "        return ret - 1\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1: return -1\n",
    "        visited = set()\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in connections:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                visited.add(i)\n",
    "                q = deque(g[i])\n",
    "                while q:\n",
    "                    j = q.popleft()\n",
    "                    visited.add(j)\n",
    "                    for k in g[j]:\n",
    "                        if k not in visited:\n",
    "                            visited.add(k)\n",
    "                            q.append(k)\n",
    "                ret += 1\n",
    "        return ret - 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections)<n-1:\n",
    "            return -1\n",
    "\n",
    "        from collections import defaultdict\n",
    "        g = defaultdict(list)\n",
    "        for a,b in connections:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "\n",
    "        visit = [False]*n  # 效率比set高\n",
    "        group = 0\n",
    "        for i in range(n):\n",
    "            # bfs\n",
    "            if visit[i]:\n",
    "                continue\n",
    "            group += 1\n",
    "            visit[i] = 1\n",
    "            stack = [node for node in g[i] if not visit[node]]\n",
    "            while len(stack):\n",
    "                top = stack.pop()\n",
    "                visit[top] = 1\n",
    "                # 不压入栈，直接就地判断\n",
    "                for node in g[top]:\n",
    "                    if not visit[node]:\n",
    "                        visit[node] = True\n",
    "                        stack.append(node)\n",
    "        return group-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class DisJointSet:\n",
    "    def __init__(self):\n",
    "        self.parent = None\n",
    "\n",
    "    def find(self):\n",
    "        if self.parent is None:\n",
    "            return self\n",
    "        self.parent = self.parent.find()\n",
    "        return self.parent\n",
    "\n",
    "    def union(self, node):\n",
    "        root1, root2 = self.find(), node.find()\n",
    "        if root1 == root2:\n",
    "            return\n",
    "        root2.parent = root1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        cnt = 0\n",
    "        nodes = [DisJointSet() for _ in range(n)]\n",
    "        for v, u in connections:\n",
    "            if nodes[v].find() == nodes[u].find():\n",
    "                cnt += 1\n",
    "            else:\n",
    "                nodes[v].union(nodes[u])\n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            s.add(nodes[i].find())\n",
    "        return len(s) - 1 if cnt >= len(s) - 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet:\n",
    "    def __init__(self, n):\n",
    "        self.father_dict = {}\n",
    "        self.size_dict = {}\n",
    "\n",
    "        for node in range(n):\n",
    "            self.father_dict[node] = node\n",
    "            self.size_dict[node] = 1\n",
    "\n",
    "    def find(self, node):\n",
    "        if (node != self.father_dict[node]):\n",
    "            father = self.find(self.father_dict[node])\n",
    "            self.father_dict[node] = father\n",
    "            return father\n",
    "        return node\n",
    "\n",
    "    def union(self, node_a, node_b):      \n",
    "        a_head = self.find(node_a)\n",
    "        b_head = self.find(node_b)\n",
    "\n",
    "        if a_head != b_head:\n",
    "            a_set_size = self.size_dict[a_head]\n",
    "            b_set_size = self.size_dict[b_head]\n",
    "            if (a_set_size >= b_set_size):\n",
    "                self.father_dict[b_head] = a_head\n",
    "                self.size_dict[a_head] = a_set_size + b_set_size\n",
    "            else:\n",
    "                self.father_dict[a_head] = b_head\n",
    "                self.size_dict[b_head] = a_set_size + b_set_size\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: [[int]]) -> int:\n",
    "        uf_set = UnionFindSet(n)\n",
    "        count = 0\n",
    "        part = n\n",
    "        for a, b in connections:\n",
    "            if not uf_set.union(a, b):\n",
    "                count += 1\n",
    "            else:\n",
    "                part -= 1\n",
    "\n",
    "        return part - 1 if count >= part - 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DisjointSet:\n",
    "    def __init__(self, n):\n",
    "        self.height = dict()\n",
    "        self.parent = dict()\n",
    "        for x in [_ for _ in range(n)]:\n",
    "            self.height[x] = 0\n",
    "            self.parent[x] = x\n",
    "    def find(self, x):\n",
    "        while (x != self.parent[x]):\n",
    "            x = self.parent[x]    \n",
    "        return x\n",
    "    def unionByHeight(self, x, y):\n",
    "        a = self.find(x)\n",
    "        b = self.find(y)\n",
    "\n",
    "        if (self.height[a] <= self.height[b]):\n",
    "            if (self.height[a] == self.height[b]):\n",
    "                self.height[b] += 1\n",
    "            self.parent[a] = b\n",
    "        else:\n",
    "            self.parent[b] = a\n",
    "    def unionByPath(self, x, y):\n",
    "        a = self.find(x)\n",
    "        b = self.find(y)\n",
    "\n",
    "        self.parent[a] = b\n",
    "    def printInfo(self):\n",
    "        print(self.height)\n",
    "        print(self.parent)\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        length = len(connections)\n",
    "        if (length < n-1):\n",
    "            return -1\n",
    "\n",
    "        ds = DisjointSet(n)\n",
    "        \n",
    "        # res = []\n",
    "        for [x, y] in connections:\n",
    "            a = ds.find(x)\n",
    "            b = ds.find(y)\n",
    "\n",
    "            if (a != b):\n",
    "                ds.unionByPath(x, y)\n",
    "\n",
    "        res = [ds.find(x) for x in ds.parent]\n",
    "        return len(set(res))-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        #关键在于如果线数量可以完全连通整个网络，那就不用担心具体怎么连的\n",
    "        #连接n个连通分支只需要操作n-1条线\n",
    "        if len(connections)<n-1:\n",
    "            return -1\n",
    "        G=[set() for _ in range(n)]\n",
    "        for i,j in connections:\n",
    "            G[i].add(j)\n",
    "            G[j].add(i)\n",
    "        seen=[0]*n\n",
    "        def dfs(i):\n",
    "            if seen[i]==1:\n",
    "                return 0\n",
    "            seen[i]=1\n",
    "            for j in G[i]:\n",
    "                dfs(j)\n",
    "            return 1\n",
    "        return sum(dfs(i) for i in range(n))-1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "        graph = defaultdict(list)\n",
    "        for [x,y] in connections:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "\n",
    "        vis = set()\n",
    "        ccs = []\n",
    "\n",
    "        queue = deque()\n",
    "\n",
    "        for i in range(n):\n",
    "            if i in graph.keys():\n",
    "                if i in vis:\n",
    "                    continue\n",
    "                cc = []\n",
    "                queue.append(i)\n",
    "                vis.add(i)\n",
    "                while(queue):\n",
    "                    x = queue.popleft()\n",
    "                    cc.append(x)\n",
    "                    for neigh in graph[x]:\n",
    "                        if neigh in vis:\n",
    "                            continue\n",
    "                        queue.append(neigh)\n",
    "                        vis.add(neigh)\n",
    "                ccs.append(cc)\n",
    "            else:\n",
    "                ccs.append([i])\n",
    "\n",
    "        return len(ccs) - 1    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "        \n",
    "        x = dict()\n",
    "        for i, j in connections:\n",
    "            if i in x:\n",
    "                x[i].append(j)\n",
    "            else:\n",
    "                x[i] = [j]\n",
    "            if j in x:\n",
    "                x[j].append(i)\n",
    "            else:\n",
    "                x[j] = [i]\n",
    "\n",
    "        block = 0\n",
    "        vis = [False] * n\n",
    "        for i in range(n):\n",
    "            if vis[i] == False:\n",
    "                queue = deque([i])\n",
    "                while queue:\n",
    "                    node = queue.popleft()\n",
    "                    vis[node] = True\n",
    "                    if node in x:\n",
    "                        for j in x[node]:\n",
    "                            if vis[j] == False:\n",
    "                                queue.append(j)\n",
    "                                vis[j] = True\n",
    "                block += 1\n",
    "\n",
    "        return block - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        m=len(connections)\n",
    "        st=set()\n",
    "        num=0\n",
    "        if m<n-1:\n",
    "            return -1\n",
    "\n",
    "        edges=collections.defaultdict(list)\n",
    "        for v in connections:\n",
    "            edges[v[0]].append(v[1])\n",
    "            edges[v[1]].append(v[0])\n",
    "        # for i ,j in connections:\n",
    "        #     edges[i].append(j)\n",
    "        #     edges[j].append(i)\n",
    "        for i in range(n):\n",
    "            if i not in st:\n",
    "                q=collections.deque([i])\n",
    "                st.add(i)\n",
    "                while q:\n",
    "                    x=q.popleft()\n",
    "                    for v in edges[x]:\n",
    "                        if v not in st:\n",
    "                            q.append(v)\n",
    "                            st.add(v)\n",
    "                num+=1\n",
    "        return num-1\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections)<n-1:\n",
    "            return -1\n",
    "        \n",
    "        from collections import defaultdict\n",
    "        g = defaultdict(list)\n",
    "        for a,b in connections:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "\n",
    "        visit = set()\n",
    "        group = 0\n",
    "        for i in range(n):\n",
    "            # bfs\n",
    "            if i in visit:\n",
    "                continue\n",
    "            group += 1\n",
    "            visit.add(i)\n",
    "            stack = [node for node in g[i] if node not in visit]\n",
    "            while len(stack)>0:\n",
    "                top = stack.pop()\n",
    "                visit.add(top)\n",
    "                stack += [node for node in g[top] if node not in visit]\n",
    "\n",
    "        return group-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if n > len(connections) + 1:\n",
    "            return -1\n",
    "        dic = defaultdict(list)\n",
    "        for a, b in connections:\n",
    "            dic[a].append(b)\n",
    "            dic[b].append(a)\n",
    "        print(dic)\n",
    "        seen = set()\n",
    "        q = []\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if i not in seen:\n",
    "                q.append(i)\n",
    "                seen.add(i)\n",
    "                while q:\n",
    "                    \n",
    "                    cur = q.pop(0)\n",
    "                    for j in dic[cur]:\n",
    "                        if j not in seen:\n",
    "                            seen.add(j)\n",
    "                            q.append(j)\n",
    "                res += 1\n",
    "        return res - 1\n",
    "           \n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        class UnionFindSet:\n",
    "            def __init__(self,nodes):\n",
    "                self.fatherDict = dict() #node:father 的字典\n",
    "                self.sizeDict = dict() #node：count 的字典\n",
    "                self.memberList = collections.defaultdict(list) #node：mebers\n",
    "                for node in nodes:\n",
    "                    self.fatherDict[node]=node\n",
    "                    self.sizeDict[node] = 1 \n",
    "                    self.memberList[node].append(node)\n",
    "            \n",
    "            #查询head并压缩\n",
    "            def findhead(self,node):\n",
    "                f_list =[]\n",
    "                father = self.fatherDict[node]\n",
    "                if node != father:\n",
    "                    father = self.findhead(father)\n",
    "                self.fatherDict[node] = father \n",
    "                return father\n",
    "            \n",
    "            #合并两个对象\n",
    "            def union(self,node_1,node_2):\n",
    "                father1 = self.findhead(node_1)\n",
    "                father2 = self.findhead(node_2)\n",
    "                \n",
    "                if father1 != father2 :\n",
    "                    num1 = self.sizeDict[father1]\n",
    "                    num2 = self.sizeDict[father2]\n",
    "                    if num1>num2 :\n",
    "                        self.fatherDict[father2] = father1\n",
    "                        self.sizeDict[father1] = num1 + num2 \n",
    "                        self.memberList[father1].extend(self.memberList[father2])\n",
    "                        self.sizeDict.pop(father2)\n",
    "                        self.memberList.pop(father2)\n",
    "                    else:\n",
    "                        self.fatherDict[father1] = father2\n",
    "                        self.sizeDict[father2] = num2 + num1\n",
    "                        self.memberList[father2].extend(self.memberList[father1])\n",
    "                        self.sizeDict.pop(father1)\n",
    "                        self.memberList.pop(father1)\n",
    "                        \n",
    "            #合并一个list\n",
    "            def unions(self,nodelist):\n",
    "                father = self.findhead(nodelist[0])\n",
    "                for node in nodelist:\n",
    "                    father0 = self.findhead(node)\n",
    "                    if father0!=father:\n",
    "                        self.fatherDict[father0]=father\n",
    "                        self.findhead(node)\n",
    "                        self.sizeDict[father]+=self.sizeDict[father0]\n",
    "                        self.sizeDict.pop(father0)\n",
    "                        self.memberList[father].extend(self.memberList[father0])\n",
    "                        self.memberList.pop(father0)\n",
    "        \n",
    "        len_l = len(connections)\n",
    "        if len_l < n-1 :\n",
    "            return -1\n",
    "        ufs_nodes = [i for i in range(n)]\n",
    "        ufs = UnionFindSet(ufs_nodes)\n",
    "        \n",
    "        for x,y in connections:\n",
    "            ufs.union(x,y)\n",
    "        print(len(ufs.sizeDict)-1)\n",
    "        return len(ufs.sizeDict)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        m = len(connections)\n",
    "        if m < n - 1:\n",
    "            return -1\n",
    "\n",
    "        visited = set()\n",
    "        graph = {i:list() for i in range(n)}\n",
    "        for a, b in connections:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "\n",
    "        ans = 0\n",
    "        for pc in graph:\n",
    "            if pc in visited:\n",
    "                continue\n",
    "            ans += 1\n",
    "            visited.add(pc)\n",
    "\n",
    "            stack = [pc]\n",
    "            while stack:\n",
    "                node = stack.pop()\n",
    "                for next_node in graph[node]:\n",
    "                    if next_node in visited:\n",
    "                        continue\n",
    "                    visited.add(next_node)\n",
    "                    stack.append(next_node)\n",
    "\n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        def find_ancestor(x):\n",
    "            if union[x] in union:\n",
    "                union[x] = find_ancestor(union[x])\n",
    "            return union[x]\n",
    "\n",
    "        def is_connected(a, b):\n",
    "            return find_ancestor(a) == find_ancestor(b)\n",
    "\n",
    "        def merge(a, b):\n",
    "            fa_a, fa_b = find_ancestor(a), find_ancestor(b)\n",
    "            union[fa_b] = fa_a\n",
    "\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "        union = {}\n",
    "        for i in range(n):\n",
    "            union[i] = -i - 1\n",
    "        size = n\n",
    "        for a, b in connections:\n",
    "            if not is_connected(a, b):\n",
    "                merge(a, b)\n",
    "                size -= 1\n",
    "        return size-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections)<n-1:return -1\n",
    "        g=[set() for _ in range(n)]\n",
    "        v=[0]*n\n",
    "        for a,b in connections:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "\n",
    "        block=0\n",
    "        for i in range(n):\n",
    "            if v[i]==0:\n",
    "                q=[i]\n",
    "                nxt=[]\n",
    "                block+=1\n",
    "                while q:\n",
    "                    s=q.pop()\n",
    "                    for t in g[s]:\n",
    "                        if v[t]==0:\n",
    "                            v[t]=1\n",
    "                            nxt.append(t)\n",
    "                    if not q:\n",
    "                        q=nxt\n",
    "                        nxt=[]\n",
    "        return block-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections)<n-1:\n",
    "            return -1\n",
    "        visited=set()\n",
    "        dic={i:set() for i in range(n)}\n",
    "        for x,y in connections:\n",
    "            dic[x].add(y)\n",
    "            dic[y].add(x)\n",
    "        count=0\n",
    "\n",
    "        from collections import deque\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                q=deque([i])\n",
    "                visited.add(i)\n",
    "                while q:\n",
    "                    node=q.popleft()\n",
    "                    for next_node in dic[node]:\n",
    "                        if next_node not in visited:\n",
    "                            visited.add(next_node)\n",
    "                            q.append(next_node)\n",
    "                count+=1\n",
    "        return count-1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return - 1\n",
    "        graph = collections.defaultdict(set)\n",
    "        for connec in connections:\n",
    "            a,b = connec\n",
    "            graph[a].add(b)\n",
    "            graph[b].add(a)\n",
    "\n",
    "        nets_num = 0\n",
    "        visited = set()\n",
    "        for i in range(n):\n",
    "            if i in visited:\n",
    "                continue\n",
    "            queue = deque()\n",
    "            queue.append(i)\n",
    "            visited.add(i)\n",
    "\n",
    "            while queue:\n",
    "                nd = queue.popleft()\n",
    "                if not nd in graph:\n",
    "                    break\n",
    "                for next_nd in graph[nd]:\n",
    "                    if not next_nd in visited:\n",
    "                        queue.append(next_nd)\n",
    "                        visited.add(next_nd)\n",
    "            nets_num += 1\n",
    "        return nets_num - 1\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        if len(connections) < n-1:\n",
    "            return -1\n",
    "\n",
    "        adj_tbl = defaultdict(set)\n",
    "        for start, end in connections:\n",
    "            adj_tbl[start].add(end)\n",
    "            adj_tbl[end].add(start)\n",
    "        \n",
    "        visited = [0] * n \n",
    "        \n",
    "        def dfs(node):\n",
    "            visited[node] = 1\n",
    "            \n",
    "\n",
    "            if node in adj_tbl:\n",
    "                for next_node in adj_tbl.get(node):\n",
    "                    if visited[next_node] == 0:\n",
    "                        dfs(next_node)\n",
    "        color = 0\n",
    "        for i in range(n):\n",
    "            # 计算联通分量数目\n",
    "            if visited[i] == 0:\n",
    "                dfs(i)\n",
    "                color +=1\n",
    "        return color - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        if len(connections) < n-1:\n",
    "            return -1\n",
    "\n",
    "        adj_tbl = defaultdict(set)\n",
    "        for start, end in connections:\n",
    "            adj_tbl[start].add(end)\n",
    "            adj_tbl[end].add(start)\n",
    "        \n",
    "        visited = [0] * n \n",
    "        \n",
    "        def dfs(node):\n",
    "            visited[node] = 1\n",
    "            \n",
    "\n",
    "            if node in adj_tbl:\n",
    "                for next_node in adj_tbl.get(node):\n",
    "                    if visited[next_node] == 0:\n",
    "                        dfs(next_node)\n",
    "        color = 0\n",
    "        for i in range(n):\n",
    "            # 计算联通分量数目\n",
    "            if visited[i] == 0:\n",
    "                dfs(i)\n",
    "                color +=1\n",
    "        return color - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "\n",
    "        g = create_graph(n, connections)\n",
    "        edges = len(connections)\n",
    "        components = get_components(g)\n",
    "        connected_check = edges - (n - components) >= components - 1 # edges >= n - 1\n",
    "\n",
    "        return components - 1 if connected_check else -1\n",
    "\n",
    "\n",
    "\n",
    "def create_graph(n, connections):\n",
    "    g = [set() for i in range(n)]\n",
    "\n",
    "    for u, v in connections:\n",
    "        g[u].add(v)\n",
    "        g[v].add(u)\n",
    "\n",
    "    return g\n",
    "\n",
    "\n",
    "def get_components(g):\n",
    "    n = len(g)\n",
    "    marked = [False] * n\n",
    "    def dfs(u):\n",
    "        marked[u] = True\n",
    "        for v in g[u]:\n",
    "            if not marked[v]:\n",
    "                dfs(v)\n",
    "\n",
    "    c = 0\n",
    "    for u in range(len(g)):\n",
    "        if not marked[u]:\n",
    "            c += 1\n",
    "            dfs(u)\n",
    "    return c\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n-1: return -1\n",
    "\n",
    "        graph = [set() for _ in range(n)]\n",
    "        for u, v in connections:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "        \n",
    "        visited = [False]*n\n",
    "        def dfs(node):\n",
    "            if visited[node]: return 0\n",
    "            visited[node] = True\n",
    "            for neigh in graph[node]: dfs(neigh)\n",
    "            return True\n",
    "        \n",
    "        return sum(dfs(node) for node in range(n)) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return - 1\n",
    "        graph = {}\n",
    "        for connec in connections:\n",
    "            a,b = connec\n",
    "            if not a in graph:\n",
    "                graph[a] = set()\n",
    "            if not b in graph:\n",
    "                graph[b] = set()\n",
    "            graph[a].add(b)\n",
    "            graph[b].add(a)\n",
    "        \n",
    "        print(graph)\n",
    "        nets_num = 0\n",
    "        visited = set()\n",
    "        for i in range(n):\n",
    "            if i in visited:\n",
    "                continue\n",
    "            queue = deque()\n",
    "            queue.append(i)\n",
    "            visited.add(i)\n",
    "\n",
    "            while queue:\n",
    "                nd = queue.popleft()\n",
    "                if not nd in graph:\n",
    "                    break\n",
    "                for next_nd in graph[nd]:\n",
    "                    if not next_nd in visited:\n",
    "                        queue.append(next_nd)\n",
    "                        visited.add(next_nd)\n",
    "            nets_num += 1\n",
    "        return nets_num - 1\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "\n",
    "        def dfs(i ,seen , graph):\n",
    "            seen.add(i)\n",
    "            for c in graph[i]:\n",
    "                if c not in seen:\n",
    "                    dfs(c , seen , graph)\n",
    "\n",
    "\n",
    "        num = len(connections)\n",
    "        if num <n-1:\n",
    "            return -1\n",
    "        else:\n",
    "            graph = defaultdict(set)\n",
    "            seen = set()\n",
    "            for u , v in connections:\n",
    "                graph[u].add(v)\n",
    "                graph[v].add(u)\n",
    "            \n",
    "            ans = -1\n",
    "            for i in range(n):\n",
    "                if i not in seen:\n",
    "                    dfs(i,seen ,graph)\n",
    "                    ans += 1\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1: return -1\n",
    "        graph = defaultdict(set)\n",
    "        seen = set()\n",
    "        def dfs(i, seen, graph):\n",
    "            seen.add(i)\n",
    "            for child in graph[i]:\n",
    "                if child not in seen:\n",
    "                    dfs(child, seen, graph)\n",
    "        for u, v in connections:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if i not in seen:\n",
    "                dfs(i, seen, graph)\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "\n",
    "        dic = defaultdict(set)\n",
    "        for i in connections:\n",
    "            dic[i[0]].add(i[1])\n",
    "            dic[i[1]].add(i[0])\n",
    "        \n",
    "        ans = set()\n",
    "        num = 0\n",
    "        \n",
    "        def dfs(n):\n",
    "            ans.add(n)\n",
    "            for j in dic[n]:\n",
    "                if j not in ans:\n",
    "                    dfs(j)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i not in ans:\n",
    "                dfs(i)\n",
    "                num += 1\n",
    "        \n",
    "        return num - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        cable_count = len(connections)\n",
    "        if cable_count < n -1:\n",
    "            return -1\n",
    "        has_dic = collections.defaultdict(set)\n",
    "        for i in connections:\n",
    "            has_dic[i[0]].add(i[1])\n",
    "            has_dic[i[1]].add(i[0])\n",
    "        visited =set()\n",
    "        res_count =0\n",
    "        def dfs(i):\n",
    "            nonlocal res_count\n",
    "            visited.add(i)\n",
    "            nex_list = has_dic[i]\n",
    "            for j in nex_list:\n",
    "                if j  in visited:\n",
    "                    res_count += 1\n",
    "                else:\n",
    "                    dfs(j)\n",
    "            return\n",
    "        count = 0\n",
    "        for c in range(n):\n",
    "            if c not in visited:\n",
    "                count +=1\n",
    "                dfs(c)\n",
    "        if res_count - count >= -1:\n",
    "            return  count -1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections)<n-1:\n",
    "            return -1\n",
    "        dic=defaultdict(set)\n",
    "        for x,y in connections:\n",
    "            dic[x].add(y)\n",
    "            dic[y].add(x)\n",
    "        res=0\n",
    "        visited=set()\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                res+=1\n",
    "                queue=deque([i])\n",
    "                while queue:\n",
    "                    j=queue.popleft()\n",
    "                    if j in dic:\n",
    "                        for k in dic[j]:\n",
    "                            if k not in visited:\n",
    "                                visited.add(k)\n",
    "                                queue.append(k)\n",
    "        return res-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # 因为n个节点最少需要n-1根线相连，所以线根据线与节点关系判断能不能连接所有电脑\n",
    "# # 接下来就是计算有多少个独立的节点，这个使用并查集来完成\n",
    "# class Solution:\n",
    "#     def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "#         if len(connections) < n - 1:\n",
    "#             return -1\n",
    "#         dic = {}\n",
    "#         def find(x):\n",
    "#             if x != dic.setdefault(x, x):\n",
    "#                 dic[x] = find(dic[x])\n",
    "#             return dic[x]\n",
    "#         for a, b in connections:\n",
    "#             dic[find(b)] = find(a)\n",
    "#         nodes = set()\n",
    "#         for i in range(n):\n",
    "#             nodes.add(find(i))\n",
    "#         return len(nodes) - 1\n",
    "\n",
    "# DFS方法，使用DFS计算独立的网络个数\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        # 先判断线是否足够多\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "        # 构建网络\n",
    "        dic = defaultdict(set)\n",
    "        for a, b in connections:\n",
    "            dic[a].add(b)\n",
    "            dic[b].add(a)\n",
    "        # 构建遍历哈希表，保证每个节点只被遍历一次\n",
    "        valid = [True] * n\n",
    "        def dfs(i):\n",
    "            if valid[i]:\n",
    "                valid[i] = False\n",
    "                for adj in dic[i]:\n",
    "                    dfs(adj)\n",
    "                return 1 # 注意这个1只有第一次遍历进入某个子网络才会返回\n",
    "            return 0\n",
    "        return sum(dfs(i) for i in range(n)) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 2023/03/02 kc\n",
    "# keys:  1. we need at least n-1 cables to connect all computers\n",
    "#        2. number of clusters - 1 is the minimum move we need to operate\n",
    "#        3. use DFS to count the number of clusters, initialize visited arr with [-1, -1, ....]\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        n_cable = len(connections)\n",
    "        if n_cable < n-1:\n",
    "            return -1\n",
    "        \n",
    "        n_cluster = 0\n",
    "        visited = [-1] * n\n",
    "        hp = defaultdict(set)\n",
    "\n",
    "        # hp has all connected computers, note: not singleton computer\n",
    "        for i in range(n_cable):\n",
    "            hp[connections[i][0]].add(connections[i][1])\n",
    "            hp[connections[i][1]].add(connections[i][0])\n",
    "        def dfs(computer):\n",
    "            if visited[computer] != -1:\n",
    "                return\n",
    "            visited[computer] = 1\n",
    "            if hp[computer]: \n",
    "                for sub in hp[computer]:\n",
    "                    dfs(sub)\n",
    "        # loop n computers\n",
    "        for i in range(n):\n",
    "            if visited[i] == -1:\n",
    "                n_cluster += 1 \n",
    "                dfs(i)\n",
    "        return n_cluster - 1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if n>len(connections)+1:\n",
    "            return -1\n",
    "        dic={i:{i} for i in range(n)}\n",
    "        lst=[i for i in range(n)]\n",
    "        for m,n in connections:\n",
    "            if m==n:\n",
    "                continue\n",
    "            #print(m,n)\n",
    "            if (lst[m] in dic and n in dic[lst[m]]) or (lst[n] in dic and m in dic[lst[n]]):\n",
    "                continue\n",
    "            else:\n",
    "                a,b=min(lst[m],lst[n]),max(lst[m],lst[n])\n",
    "                dic[a]=dic[a].union(dic[b])\n",
    "                for x in dic[b]:\n",
    "                    lst[x]=a\n",
    "                del dic[b]\n",
    "                lst[m]=lst[n]=a\n",
    "            #print(lst)\n",
    "            #print(dic)\n",
    "        return len(dic)-1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n-1:\n",
    "            return -1\n",
    "        nex = {i:set() for i in range(n)}\n",
    "        for u,v in connections:\n",
    "            nex[u].add(v)\n",
    "            nex[v].add(u)\n",
    "        vis = set()\n",
    "        group = 0\n",
    "        def conn(u):\n",
    "            if u in vis:\n",
    "                return\n",
    "            vis.add(u)\n",
    "            for v in nex[u]:\n",
    "                conn(v)\n",
    "                \n",
    "        for i in range(n):\n",
    "            if i in vis:\n",
    "                continue\n",
    "            conn(i)\n",
    "            group += 1\n",
    "        return group-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 首先求出有几个联通分量\n",
    "    # 然后求出有多少个多余的边\n",
    "    # 如果多余的边>=联通分量-1, 返回联通分量-1\n",
    "    def cal_components(self, n, nondirected_graph ):\n",
    "        visited = set()\n",
    "        components = 0\n",
    "        for i in range(n):\n",
    "            if i in visited: continue\n",
    "            queue = [i]\n",
    "            components+=1\n",
    "            while queue:\n",
    "                node = queue.pop(0)\n",
    "                if node not in visited:\n",
    "                    visited.add(node)\n",
    "                    for sub_n in nondirected_graph[node]:\n",
    "                        queue.append(sub_n)\n",
    "        return components\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        nondirected_graph = collections.defaultdict(list)\n",
    "        for conn in connections:\n",
    "            graph[conn[0]].append(conn[1])\n",
    "            nondirected_graph[conn[0]].append(conn[1])\n",
    "            nondirected_graph[conn[1]].append(conn[0])\n",
    "        visited = set()\n",
    "        redundants = 0\n",
    "        components = self.cal_components(n, nondirected_graph)\n",
    "        for i in range(n):\n",
    "            if i in visited: continue\n",
    "            queue = [i]\n",
    "            while queue:\n",
    "                node = queue.pop(0)\n",
    "                if node not in visited:\n",
    "                    visited.add(node)\n",
    "                    for sub_n in graph[node]:\n",
    "                        queue.append(sub_n)\n",
    "                else:\n",
    "                    redundants+=1\n",
    "        if redundants>=components-1: return components-1\n",
    "        else: return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "# 如果线不够，怎么都没法连，如果线够，怎么都能连上。先数有多少个联通块，需要（联通块-1）条线去连接所有联通块\n",
    "# 最后全连起来就只有1个联通块了，其他的联通块都需要使用一条cable连接（线肯定够用），所以需要调整的cable数是（联通块-1）\n",
    "    def makeConnected(self, n, connections): # 方法一：BFS, time O(m + n), space O(n), m is the length of connections\n",
    "        # We need at least n - 1 cables to connect all nodes (like a tree). So if connections.size() < n - 1, we can directly return -1.\n",
    "        if len(connections) < n - 1: \n",
    "            return -1 \n",
    "        def bfs(node, graph, visited):\n",
    "            dq = collections.deque([node])\n",
    "            while dq:\n",
    "                curr = dq.popleft()\n",
    "                for nei in graph[curr]:\n",
    "                    if nei not in visited:\n",
    "                        dq.append(nei)\n",
    "                        visited.add(nei)\n",
    "            return \n",
    "        graph = collections.defaultdict(set)\n",
    "        for u, v in connections:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "        connected_components = 0\n",
    "        visited = set()\n",
    "        for node in range(n):\n",
    "            if node not in visited:\n",
    "                visited.add(node)\n",
    "                bfs(node, graph, visited)\n",
    "                connected_components += 1\n",
    "        # n components need n-1 calbes to connect them together and form as a single large component. \n",
    "        # Finally, there is only one component. minus 1 indicates connecting all other components to this component\n",
    "        return connected_components - 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "        st = [0] * n\n",
    "        ans = 0\n",
    "        g = [[] for _ in range(n)]\n",
    "        for [a, b] in connections:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        def dfs(x: int):\n",
    "            st[x] = 1\n",
    "            for y in g[x]:\n",
    "                if st[y] == 0: \n",
    "                    dfs(y)\n",
    "        for i in range(n):\n",
    "            if st[i] == 0:\n",
    "                dfs(i)\n",
    "                ans += 1\n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        edge = {_:set() for _ in range(n)}\n",
    "\n",
    "        for e in connections:\n",
    "            a, b = e\n",
    "            edge[a].add(b)\n",
    "            edge[b].add(a)\n",
    "        \n",
    "        Q = []\n",
    "        visited = [0] * n\n",
    "        graphs = [] \n",
    "        for i in edge:\n",
    "            if visited[i] == 1:\n",
    "                continue\n",
    "            Q = [i]\n",
    "            visited[i] = 1\n",
    "            graph = {i}\n",
    "            count_edges = 0\n",
    "            while len(Q):\n",
    "                x = Q.pop(0)\n",
    "                \n",
    "                for y in edge[x]:\n",
    "                    if visited[y] != 1:\n",
    "                        Q.append(y)\n",
    "                        visited[y] = 1\n",
    "                        graph.add(y)\n",
    "                        count_edges += 1\n",
    "            graphs.append((graph,count_edges))\n",
    "        res = 0\n",
    "        g = len(graphs)\n",
    "        for item in graphs:\n",
    "            graph, count_edges = item\n",
    "            all_edges = 0\n",
    "            for x in graph:\n",
    "                all_edges += len(edge[x])\n",
    "            res += all_edges // 2 - count_edges\n",
    "        \n",
    "        if res >= g - 1:\n",
    "            return g - 1\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1: return -1\n",
    "        graph = defaultdict(set)\n",
    "        seen = set()\n",
    "        def dfs(i, seen, graph):\n",
    "            seen.add(i)\n",
    "            for child in graph[i]:\n",
    "                if child not in seen:\n",
    "                    dfs(child, seen, graph)\n",
    "        for u, v in connections:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if i not in seen:\n",
    "                dfs(i, seen, graph)\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1: return -1\n",
    "        graph = defaultdict(set)\n",
    "        seen = set()\n",
    "        def dfs(i, seen, graph):\n",
    "            seen.add(i)\n",
    "            for child in graph[i]:\n",
    "                if child not in seen:\n",
    "                    dfs(child, seen, graph)\n",
    "        for u, v in connections:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if i not in seen:\n",
    "                dfs(i, seen, graph)\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        cableCount = len(connections)\n",
    "        if cableCount < n-1:\n",
    "            return -1\n",
    "        \n",
    "        graph = [[] for _ in range(n)]\n",
    "        for c1, c2 in connections:\n",
    "            graph[c1].append(c2)\n",
    "            graph[c2].append(c1)\n",
    "        \n",
    "        parts = 0\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(index: int):\n",
    "            visited.add(index)\n",
    "            for i in graph[index]:\n",
    "                if not i in visited:\n",
    "                    dfs(i)\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            if not i in visited:\n",
    "                parts += 1\n",
    "                dfs(i)\n",
    "        \n",
    "        return parts-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n-1:\n",
    "            return -1\n",
    "        \n",
    "        g = collections.defaultdict(list)\n",
    "        for x, y in connections:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        vis = set()\n",
    "        def dfs(x):\n",
    "            for y in g[x]:\n",
    "                if not y in vis:\n",
    "                    vis.add(y)\n",
    "                    dfs(y)\n",
    "        \n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if not i in vis:\n",
    "                cnt += 1\n",
    "                dfs(i)\n",
    "        \n",
    "        return cnt-1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n # 每个并查集的大小\n",
    "        self.n = n\n",
    "        # 当前并查集数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        # # 并查集\n",
    "        # m = len(connections)\n",
    "        # if m < n - 1:\n",
    "        #     return -1\n",
    "        \n",
    "        # uf = UnionFind(n)\n",
    "        # for x, y in connections:\n",
    "        #     uf.unite(x, y)\n",
    "        \n",
    "        # return uf.setCount - 1\n",
    "\n",
    "        # 深度优先搜索\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "        self.edges = collections.defaultdict(list) # 先构建每节点的联通数组\n",
    "        for x, y in connections:\n",
    "            self.edges[x].append(y)\n",
    "            self.edges[y].append(x)\n",
    "        self.seen = set()\n",
    "        ans = 0\n",
    "        for i in range(n): # 遍历所有节点以及连通节点\n",
    "            if i not in self.seen:\n",
    "                self.dfs(i)\n",
    "                ans += 1\n",
    "        return ans - 1\n",
    "\n",
    "    def dfs(self, u):\n",
    "            self.seen.add(u)\n",
    "            for v in self.edges[u]: # 递归遍历连通节点\n",
    "                if v not in self.seen:\n",
    "                    self.dfs(v)\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "        \n",
    "        vis = set()\n",
    "        maps = collections.defaultdict(list)\n",
    "\n",
    "        for x, y in connections:\n",
    "            maps[x].append(y)\n",
    "            maps[y].append(x)\n",
    "\n",
    "        \n",
    "        def dfs(x):\n",
    "            vis.add(x)\n",
    "            for y in maps[x]:\n",
    "                if y not in vis:\n",
    "                    dfs(y)\n",
    "        \n",
    "        res = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in vis:\n",
    "                dfs(i)\n",
    "                res += 1\n",
    "        return res - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "\n",
    "        vis = [False] * n\n",
    "        g = collections.defaultdict(list)\n",
    "        for s, t in connections:\n",
    "            g[s].append(t)\n",
    "            g[t].append(s)\n",
    "        \n",
    "        def dfs(x, vis):\n",
    "            vis[x] = True\n",
    "            for j in g[x]:\n",
    "                if not vis[j]:\n",
    "                    dfs(j, vis)\n",
    "\n",
    "        domains = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                domains += 1\n",
    "                dfs(i, vis)\n",
    "\n",
    "        return domains - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if(len(connections)<n-1):\n",
    "            return -1\n",
    "        edges = [[] for _ in range(n)]\n",
    "        for x,y in connections:\n",
    "            edges[x].append(y)\n",
    "            edges[y].append(x)\n",
    "        # print(edges)\n",
    "        seen = [0]*n\n",
    "        ans = 0\n",
    "        def dfs(u):\n",
    "            nonlocal seen\n",
    "            seen[u] = 1\n",
    "            for v in edges[u]:\n",
    "                if seen[v]==0:\n",
    "                    dfs(v)\n",
    "\n",
    "        for i in range(n):\n",
    "            if seen[i]==0:\n",
    "                dfs(i)\n",
    "                ans +=1\n",
    "        return ans-1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        E = len(connections)\n",
    "        if E < n-1:\n",
    "            return -1\n",
    "\n",
    "        neighs = [[] for _ in range(n)]\n",
    "        for i, j in connections:\n",
    "            neighs[i].append(j)\n",
    "            neighs[j].append(i)\n",
    "\n",
    "        vis = [False for _ in range(n)]\n",
    "        def dfs(i):\n",
    "            vis[i] = True\n",
    "            for j in neighs[i]:\n",
    "                if not vis[j]:\n",
    "                    dfs(j)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                dfs(i)\n",
    "                ans += 1\n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in connections:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        vis = set()\n",
    "        def dfs(i):\n",
    "            vis.add(i)\n",
    "            for j in g[i]:\n",
    "                if j not in vis:\n",
    "                    dfs(j)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if i not in vis:\n",
    "                dfs(i)\n",
    "                res += 1\n",
    "        return res - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "\n",
    "        seen = set()\n",
    "\n",
    "        def fun1(i):\n",
    "            seen.add(i)\n",
    "            for j in l1[i]:\n",
    "                if j not in seen:\n",
    "                    fun1(j)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        l1 = [[] for _ in range(n)]\n",
    "        for x, y in connections:\n",
    "            l1[x].append(y)\n",
    "            l1[y].append(x)\n",
    "        for i in range(n):\n",
    "            if i not in seen:\n",
    "                fun1(i)\n",
    "                ans += 1\n",
    "\n",
    "        return ans - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        #求有几个连通分量就完事了，然后把多余的线分配走，你想想如果有一系列连通分量，如果是有多的一定多在某部分，多的去掉就行了，因为是\n",
    "        #简单图\n",
    "        children=[[] for i in range(n)]\n",
    "        for x,y in connections:\n",
    "            children[x].append(y)\n",
    "            children[y].append(x)\n",
    "        cnt=0\n",
    "        def dfs(i,vis):\n",
    "            vis[i]=1\n",
    "            for child in children[i]:\n",
    "                if vis[child]==1:\n",
    "                    continue\n",
    "                vis[child]=1\n",
    "                dfs(child,vis)\n",
    "            return\n",
    "        vis=[0 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            if vis[i]==1:\n",
    "                continue\n",
    "            cnt+=1\n",
    "            dfs(i,vis)\n",
    "        if len(connections)<n-1:\n",
    "            return -1\n",
    "        return cnt-1\n",
    "        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        adj = [[] for _ in range(n)]  # 邻接表\n",
    "        for x, y in connections:  # 构造邻接表，无向图\n",
    "            adj[x].append(y)\n",
    "            adj[y].append(x)\n",
    "        \n",
    "        visited = [False for _ in range(n)]  # 访问列表\n",
    "        connected_component = 0  # 连通分量的数量\n",
    "        def dfs(i):  # 深度优先搜索，对于某个接点，深度搜索它的邻接表中的所有未被节点\n",
    "            visited[i] = True\n",
    "            for y in adj[i]:\n",
    "                if visited[y] == False:\n",
    "                    dfs(y)\n",
    "\n",
    "        \n",
    "        for i in range(n):  # 搜索\n",
    "            if visited[i] == False:\n",
    "                connected_component += 1\n",
    "                dfs(i)\n",
    "        \n",
    "        return connected_component-1 if len(connections) >= n-1 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    1. remove one edge can break a circle \n",
    "    2. one edge can connect one more computer\n",
    "    3. find the number of circles and the number of computers waiting to be connected; then \n",
    "    '''\n",
    "\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n-1:\n",
    "            return -1\n",
    "        visited = [False for _ in range(n)]\n",
    "        graph = [[] for _ in range(n)] # index: computer, value: a list of the adjcent computers\n",
    "        group = 0\n",
    "\n",
    "        for i in connections:\n",
    "            graph[i[0]].append(i[1])\n",
    "            graph[i[1]].append(i[0])\n",
    "\n",
    "        for computer in range(n):\n",
    "            if visited[computer]:\n",
    "                continue \n",
    "            self.dfs(computer, visited, graph)\n",
    "            group += 1\n",
    "        \n",
    "        return group - 1\n",
    "\n",
    "    def dfs(self, node, visited, graph): # node: current computer\n",
    "        visited[node] = True \n",
    "        \n",
    "        for next_node in graph[node]:\n",
    "            if visited[next_node]:\n",
    "                continue\n",
    "            self.dfs(next_node, visited, graph)\n",
    "\n",
    "\n",
    "        # print(len(connections))\n",
    "\n",
    "        # graph = [[]for _ in range(n)] \n",
    "        # visited = [False for _ in range(n)]\n",
    "        # for i in connections:\n",
    "        #     graph[i[0]].append(i[1])\n",
    "        #     graph[i[1]].append(i[0])\n",
    "\n",
    "        # q = deque() \n",
    "        # for i in range(len(graph)):\n",
    "        #     if graph[i] != []:\n",
    "        #         q.append(i)\n",
    "        #         visited[i] = True\n",
    "        #         break \n",
    "\n",
    "        # #print(graph)\n",
    "        # while q: \n",
    "        #     cur = q.popleft()\n",
    "\n",
    "        #     for i in graph[cur]:\n",
    "        #         if not visited[i]:\n",
    "        #             q.append(i) \n",
    "        #             visited[i] = True\n",
    "\n",
    "        # print(visited)\n",
    "\n",
    "        # count = 0\n",
    "        # for i in visited:\n",
    "        #     if not i:\n",
    "        #         count += 1\n",
    "        # return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for a, b in connections:\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(i):\n",
    "            visited.add(i)\n",
    "            for j in adj[i]:\n",
    "                if j not in visited:\n",
    "                    dfs(j)\n",
    "            return\n",
    "        \n",
    "        group = 0\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                group += 1\n",
    "        return group - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        \n",
    "\n",
    "\n",
    "        m=len(connections)\n",
    "        if n>m+1:\n",
    "            return -1\n",
    "        edges = collections.defaultdict(list)\n",
    "        for x, y in connections:\n",
    "            edges[x].append(y)\n",
    "            edges[y].append(x)\n",
    "\n",
    "        v=set()\n",
    "        q=-1\n",
    "        def dfs(i):\n",
    "            v.add(i)\n",
    "            for i in edges[i]:\n",
    "                if i not in v:\n",
    "                    dfs(i)\n",
    "        for i in range(n):\n",
    "            if i not in v:\n",
    "                q+=1\n",
    "                dfs(i)\n",
    "        return q\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "        \n",
    "        edges = collections.defaultdict(list)\n",
    "        for x, y in connections:\n",
    "            edges[x].append(y)\n",
    "            edges[y].append(x)\n",
    "        \n",
    "        seen = set()\n",
    "\n",
    "        def dfs(u: int):\n",
    "            seen.add(u)\n",
    "            for v in edges[u]:\n",
    "                if v not in seen:\n",
    "                    dfs(v)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i not in seen:\n",
    "                dfs(i)\n",
    "                ans += 1\n",
    "        \n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        edges = defaultdict(list)\n",
    "        for p, q in connections:\n",
    "            edges[p].append(q)\n",
    "            edges[q].append(p)\n",
    "        visited = [0] * n\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal visited\n",
    "            if not visited[node]:\n",
    "                visited[node] = 1\n",
    "                for neighbor in edges[node]:\n",
    "                    dfs(neighbor)\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                cnt += 1\n",
    "                dfs(i)\n",
    "        e = len(connections)\n",
    "        if e < n-1:\n",
    "            return -1\n",
    "        return cnt - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "        \n",
    "        edges = collections.defaultdict(list)\n",
    "        for x, y in connections:\n",
    "            edges[x].append(y)\n",
    "            edges[y].append(x)\n",
    "        \n",
    "        seen = set()\n",
    "\n",
    "        def dfs(u: int):\n",
    "            seen.add(u)\n",
    "            for v in edges[u]:\n",
    "                if v not in seen:\n",
    "                    dfs(v)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i not in seen:\n",
    "                dfs(i)\n",
    "                ans += 1\n",
    "        \n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        #计算连通子图的数量\n",
    "        m=len(connections)\n",
    "        if m<n-1:\n",
    "            return -1\n",
    "        graph={i:[] for i in range(n)}\n",
    "        for u,v in connections:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        visited=[0]*n\n",
    "        def dfs(node):\n",
    "            for adjNode in graph[node]:\n",
    "                if not visited[adjNode]:\n",
    "                    visited[adjNode]=1\n",
    "                    dfs(adjNode)\n",
    "        cnt=0\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                visited[i]=1\n",
    "                cnt+=1\n",
    "                dfs(i)\n",
    "        return cnt-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "        graph = defaultdict(list)\n",
    "        for [x, y] in connections:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        \n",
    "        visisted = set()\n",
    "        ccs = 0\n",
    "        def dfs(id):\n",
    "            visisted.add(id)\n",
    "            for neighbor in graph[id]:\n",
    "                if neighbor in visisted:\n",
    "                    continue\n",
    "                dfs(neighbor)\n",
    "\n",
    "        for i in range(n):\n",
    "            if i in graph.keys():\n",
    "                if i in visisted:\n",
    "                    continue\n",
    "                dfs(i)\n",
    "                ccs += 1\n",
    "            else:\n",
    "                ccs +=1\n",
    "        return ccs - 1      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "        graph = defaultdict(list)\n",
    "        for [x, y] in connections:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        \n",
    "        visisted = set()\n",
    "        ccs = []\n",
    "        def dfs(id, cc):\n",
    "            visisted.add(id)\n",
    "            cc.append(id)\n",
    "            for neighbor in graph[id]:\n",
    "                if neighbor in visisted:\n",
    "                    continue\n",
    "                dfs(neighbor, cc)\n",
    "\n",
    "        for i in range(n):\n",
    "            if i in graph.keys():\n",
    "                if i in visisted:\n",
    "                    continue\n",
    "                cc = []\n",
    "                dfs(i, cc)\n",
    "                ccs.append(cc)\n",
    "            else:\n",
    "                ccs.append([i])\n",
    "        return len(ccs) - 1      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n",
    "        if len(connections) < n - 1:\n",
    "            return -1\n",
    "        \n",
    "        edges = collections.defaultdict(list)\n",
    "        for x, y in connections:\n",
    "            edges[x].append(y)\n",
    "            edges[y].append(x)\n",
    "        \n",
    "        seen = set()\n",
    "\n",
    "        def dfs(u: int):\n",
    "            seen.add(u)\n",
    "            for v in edges[u]:\n",
    "                if v not in seen:\n",
    "                    dfs(v)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i not in seen:\n",
    "                dfs(i)\n",
    "                ans += 1\n",
    "        \n",
    "        return ans - 1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
